package Hot100;

import common.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-01-07 10:53
 *
 * 297. 二叉树的序列化与反序列化
 * 1、先序遍历
 * 2、后序遍历
 * 3、层序遍历
 */
public class Codec297 {
    //序列化
    StringBuffer sb=new StringBuffer();
    public String serialize(TreeNode root) {
        if (root==null) return "";
        preOrder(root);
        return sb.toString();
    }
    void preOrder(TreeNode root){
        if (root==null) {
            sb.append("#").append(",");
            return;
        }
        sb.append(root.val).append(",");
        preOrder(root.left);
        preOrder(root.right);
    }
    // Decodes your encoded data to tree.反序列化
    public TreeNode deserialize(String data) {
        if (data.length()==0) return null;
        String[] nodes = data.split(",");
        LinkedList<String> node=new LinkedList<>();
        for (String ss:nodes) {
            node.add(ss);
        }
        return predese(node);
    }
    TreeNode predese(LinkedList<String> nodes){
        if (nodes.isEmpty()) return null;
        String first = nodes.removeFirst();
        if (first.equals("#")){
            return null;
        }
        TreeNode root=new TreeNode(Integer.parseInt(first));
        root.left=predese(nodes);
        root.right=predese(nodes);
        return root;
    }
}
